import java.util.Arrays;

//实现一个优先级队列（堆）
public class MyPriorityQueue {
    //给到一个数组，将这个数组实现大小根堆
    public int[] heap;
    public int usedSize;
    public int capacity;
    public MyPriorityQueue() {
        heap = new int[10];
        capacity = heap.length;
    }
    //给数组中的位置赋值
    public void init(int[] elem){
        for(int i = 0; i < elem.length; i++){
            heap[i] = elem[i];
            usedSize++;
        }
    }
    //根据已拥有的数据创建一个大根堆
    public void createHeap(){
        //先确定最后一课子树的父亲节点的位置
        for(int parent = (usedSize-1-1)/2;parent >= 0; parent--){
            siftDown(parent,usedSize);
        }
    }
    //向下调整 O(N)
    private void siftDown(int parent,int usedSize){
        int child = parent*2+1;
        while(child < usedSize){
            if(child+1 < usedSize && heap[child] < heap[child+1]){
                child++;
            }
            if(heap[child] > heap[parent]){
                int temp = heap[parent];
                heap[parent] = heap[child];
                heap[child] = temp;
                parent = child;
                child = parent*2+1;
            }else {
                break;
            }
        }
    }
//    //根据已拥有的数据创建一个小根堆
//    public void createHeapS(){
//        //先确定最后一课子树的父亲节点的位置
//        for(int parent = (usedSize-1-1)/2;parent >= 0; parent--){
//            siftDown(parent);
//        }
//    }
//    //向下调整
//    private void siftDown(int parent){
//        int child = parent*2+1;
//        while(child < usedSize){
//            if(child+1 < usedSize && heap[child] > heap[child+1]){
//                child++;
//            }
//            if(heap[child] < heap[parent]){
//                int temp = heap[parent];
//                heap[parent] = heap[child];
//                heap[child] = temp;
//                parent = child;
//                child = parent*2+1;
//            }else {
//                break;
//            }
//        }
//    }
    //向上调整 O(N*logN)
    public void siftUp(int child){
        int parent = (child-1)/2;
        while(parent > 0){
            if(child+1 < usedSize && heap[child] < heap[child+1]){
                child++;
            }
            if(heap[child] > heap[parent]){
                int temp = heap[parent];
                heap[parent] = heap[child];
                heap[child] = temp;
                child = parent;
                parent =(child - 1)/2;
            }else {
                break;
            }
        }
    }
    //入堆
    public void offer(int val){
        //首先检查堆是否已经满了
        if(isFull()){
            grow();
        }
        heap[usedSize] = val;
        usedSize++;
        siftUp(usedSize);
    }
    //扩容
    private void grow(){
        heap = Arrays.copyOf(heap, (int) (capacity * 1.5));
        capacity = (int) (capacity * 1.5);
    }

    //检查是否容量已满
    private boolean isFull(){
        return usedSize == heap.length;
    }

    //打印出堆中的数据
    public void display(){
        for(int i = 0; i < usedSize; i++){
            System.out.print(heap[i] + " ");
        }
        System.out.println();
    }

    /**
     * 出堆【删除】：每次删除的都是优先级高的元素
     * 仍然要保持是大根堆
     */
    public int poll() throws Exception {
        if(isEmpty()){
            throw new Exception("当前堆为空，无法删除数据!!!");
        }
        int ret = heap[usedSize - 1];
        heap[usedSize - 1] = heap[0];
        heap[0] = ret;
        ret = heap[usedSize - 1];
        usedSize--;
        siftDown(0,usedSize);
        return ret;
    }

    /**
     * 检查堆是否为空
     * @return
     */
    public boolean isEmpty() {
        return usedSize == 0;
    }

    /**
     * 获取堆顶元素
     * @return
     */
    public int peekHeap() throws Exception {
        if(isEmpty()){
            throw new Exception("堆为空，堆顶没有元素");
        }
        return heap[0];
    }
    //堆排序(从小到大排序)O(N*logN)
    public void heapSort(){
        for(int end = usedSize - 1; end > 0; end--){
            //交换0下标和end下标的元素
            int tmp = heap[0];
            heap[0] = heap[end];
            heap[end] = tmp;
            siftDown(0,end);
        }

    }
}
